googologywikiaorg-20200223-history
Introduction to ordinal collapsing functions
Feel free to add and remove which ordinals and subsections are added. Also, please add precise definitions for the OCFs. We want them to be as simple as possible, and also easy to explain. Description of OCFs and why they're needed Fast-growing hierarchy is a general framework to create a large function from an ordinal equipped with a system of fundamental sequences. Since ordinals are possibly transfinite, the resulting large functions are not necessarily computable. In order to ensure the computability, we need an ordinal notation equipped with a recursive system of fundamental sequences. Beginners should be careful that many googologists state that functions in fast-growing hierarchy is trivially computable even if we do not have an ordinal notation, but there are many known counterexamples. An ordinal notation is a countable set \(OT\) (with a fixed enumeration so that the recursiveness makes sense) equipped with a recursive well-ordering \(<\) on \(OT\). A term \(t \in OT\) itself is not necessarily an ordinal, while it corresponds the ordinal type of the segment \(I_t := \{s \in OT \mid s < t\}\), i.e. the unique ordinal \(\alpha_t\) admitting a unique order-preserving bijective map \(\alpha_t \to I_t\). Beginners should be very careful that many googologists confound the notion of an ordinal notation with other related notions such as ordinals, OCFs, notations with fundamental sequences, and so on. In order to create an ordinal notation, we usually define "the normal form" of expressions of an ordinal with respect to fixed collection of constants and functions. The most elementary example is Cantor's normal form, where ordinals below \(\varepsilon_0\) are represented as a finite decreasing sum of multiples of powers of omega, whose exponents are also ordinals represented in cantor's normal form. Using Cantor's normal form, we can interpret ordinals into formal strings. Then we can define \(OT\) as the set of formal strings corresponding to normal form expressions of ordinals below its limit called \(\varepsilon_0\), and \(<\) as the relation on formal strings corresponding to \(\in\). A non-trivial fact is that the well-ordering \(<\) is recursive, i.e. computable by only using information of formal strings instead of other non-recursive structures such as the ordinal type. Next, new functions can be invented, like the epsilon function \(\alpha \mapsto \varepsilon_{\alpha}\) enumerating the fixed points (epsilon numbers) of \(\alpha \mapsto \omega^{\alpha}\), the zeta function \(\alpha \mapsto \zeta_{\alpha}\) enumerating its fixed points (zeta numbers), the eta function \(\alpha \mapsto \eta_{\alpha}\) enumerating the fixed points (eta numbers) of that! Then, they can be generalized into the Veblen phi function \(\varphi(\alpha,\beta)\). The gamma function enumerates the fixed points (gamma numbers or strictly critical ordinals) of \(\alpha \mapsto \varphi(\alpha,0)\). The gamma function is a extended to the multi-argument Veblen phi function which has multiple arguments, which can then be extended to transfinite arguments. Those functions except for transfinite arguments admit the notion of "the normal form". Similar to the ordinal notation associated to Cantor's normal form, the set \(OT\) of formal strings corresponding to normal form expressions with respect to the functions forms an ordinal notation, i.e. the well-ordering \(<\) on \(OT\) corresponding to \(\in\) is recursive. Now you could extend it even further, rather naively. Or you could create an ordinal collapsing function. An ordinal collapsing function takes uncountable ordinals as input and outputs countable ordinals. Beginners should be very careful that defining functions and normal forms does not ensure the recursiveness of the well-ordering \(<\) on the set of formal strings corresponding to normal form expressions. In order to verify the recursiveness of \(<\), we need to fix an enumeration of \(OT\), which can be omitted as long as \(OT\) is a recursive set of formal strings with respect to the lexicographic ordering, and explicitly construct an algorithm which computes the \(<\) relation by only using information of formal strings. Since the \(\in\) relation itself is not recursive, the lack of such an algorithm can be a serious issue. The following are examples of OCFs. As we explained above, please be careful that functions such as OCFs themselves do not automatically yield the notion of "the normal form" and an associated ordinal notation. In particular, the notion of "the normal form" or an associated ordinal notation might be undefined for an OCF below. Madore's psi Madore's psi is defined like this: \begin{eqnarray*} C_0(\alpha) &=& \{0, 1, \omega, \Omega\}\\ C_{n+1}(\alpha) &=& \{\gamma + \delta, \gamma\delta, \gamma^{\delta}, \psi(\eta) | \gamma, \delta, \eta \in C_n (\alpha); \eta < \alpha\} \\ C(\alpha) &=& \bigcup_{n < \omega} C_n (\alpha) \\ \psi(\alpha) &=& \min\{\beta \in \Omega|\beta \notin C(\alpha)\} \\ \end{eqnarray*} This looks quite cryptic, so here is a less technical definition: Let \(C(\alpha)\) be the set of all ordinals that can be expressed in terms of \(0, 1, \omega, \Omega\) and the operations addition, multiplication, exponentiation, and \(\kappa\rightarrow\psi(\kappa)\), the latter only if \(\kappa\) is less than \(\alpha\). \(\psi(\alpha)\) is the first ordinal not in \(C(\alpha)\). For inputs below \(\Omega\) the function is equivalent to \(\varepsilon_x\) and \(\psi(\Omega)\) is equal to \(\zeta_0\). This function is limited at the Bachmann-Howard ordinal. Up next we will explain another commonly-used ordinal collapsing function. Bachmann-Howard ordinal Let \(\Omega=\omega_1\) be the smallest uncountable ordinal. \(\begin{eqnarray*} C_0(\alpha,\beta) &=& \beta\cup\{\Omega\} \\ C_{n+1}(\alpha,\beta) &=& \{\gamma+\delta:\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\omega^\gamma:\gamma\in C_n(\alpha,\beta)\wedge\gamma\geq\Omega\} \\ &\cup& \{\vartheta(\gamma):\gamma\in C_n(\alpha,\beta)\wedge\gamma<\alpha\} \\ C(\alpha,\beta) &=& \bigcup_{n<\omega}C_n(\alpha,\beta) \end{eqnarray*}\) \(C(\alpha,\beta)\) can also be seen as the closure of \(\{\Omega\}\) and all of the ordinals less than \(\beta\) under addition, base-\(\omega\) exponentiation (to uncountable ordinals), and the \(\vartheta\) function to ordinals less than \(\alpha\). \(\vartheta(\alpha) = \min\{\beta>0:\Omega\cap C(\alpha,\beta)\subseteq\beta\}\) \(\vartheta(\alpha)\) can also be seen as the smallest ordinal \(\beta\) such that all countable ordinals in \(C(\alpha,\beta)\) are less than \(\beta\); \(\beta\) is the smallest ordinal such that you can't create a larger countable ordinal from the ordinals less than \(\beta\), \(\Omega\), and the operations \(+\), \(\gamma\mapsto\omega^\gamma\) (for \(\gamma\geq\Omega\)), and \(\gamma\mapsto\vartheta(\gamma)\) (for \(\gamma<\alpha\)). Now, let's say that we are trying to find \(\vartheta(\alpha)\), where \(\alpha\) is some countable ordinal. Fundamental sequences Takeuti-Feferman-Buchholz ordinal extensions of the theta and psi functions Fundamental sequences SGH vs. FGH \(\vartheta(\Phi(1,0))\) Same as \(\psi(\psi_I(0))\), but doesn't need explanation of \(I\). \(\Phi\) is the Veblen function on \(\alpha\mapsto\omega_\alpha\) Fundamental sequences \(\psi(\Lambda_0)\) Note: For this section, to make understanding the cardinals easier, we drop 'weakly' from the definitions of \(\alpha\)-inaccessibility, and simply have the \(\alpha\)-inaccessible cardinals mean the weakly \(\alpha\)-inaccessibles, not the strongly \(\alpha\)-inaccessibles. This removes potential confusion. Call a cardinal \(0\)-inaccessible iff it is uncountable and regular. Now, call a cardinal \(\alpha+1\)-inaccessible iff it is \(\alpha\)-inaccessible and a limit of \(\alpha\)-inaccessible cardinals, and, for limit ordinals \(\lambda\), call a cardinal \(\lambda\)-inaccessible if it is \(\alpha\)-inaccessible for all \(\alpha<\lambda\). Lastly, we can call a cardinal \(\kappa\) which is \(\kappa\)-inaccessible hyper-inaccessible and let \(\Lambda_0\) be the smallest hyper-inaccessible cardinal. Although not relevant to the definition directly, please not that it's impossible to prove that even a \(1\)-inaccessible cardinal exists in ZFC. Therefore, for this section, we instead work in the system ZFC + 'there exists a hyper-inaccessible cardinal'. Now, we can define a series of functions, \(\text I_\alpha\), which enumerate the \(\alpha\)-inaccessible cardinals less than \(\Lambda_0\), and their limit points. Formally, we write: \(\text I_\alpha = \text{enum}(\text{cl}(\{\beta<\Lambda_0:\beta\text{ is }\alpha\text{-inaccessible}\}))\) Where \(\text{enum}(S)\) is the unique increasing function that enumerates the elements of \(S\) (so \(\text{enum}(\{\omega^3,\omega^4,\omega^5,\cdots,\omega^{\omega^2},\omega^{\omega^2+1}\})\) is the function \(\alpha\mapsto\omega^{3+\alpha}\) defined on \(\omega^2+2\mapsto S\))), and \(\text{cl}(S)\) is \(S\cup\{\beta:\sup(S\cap\beta)=\beta\}\): the union of \(S\) and it's limit points. Also, similarly to last time, restrict \(\pi\) to uncountable regular cardinals (equivalently: \(0\)-inaccessible). With this, we can define our \(\psi\) function: \(\begin{eqnarray*} C_0(\alpha,\beta) &=& \beta \\ C_{n+1}(\alpha,\beta) &=& \{\gamma+\delta:\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\text I_\gamma(\delta):\gamma,\delta\in C_n(\alpha,\beta)\} \\ &\cup& \{\psi_\pi(\gamma):\gamma,\pi\in C_n(\alpha,\beta)\wedge\gamma<\alpha\} \\ C(\alpha,\beta) &=& \bigcup_{n<\omega}C_n(\alpha,\beta) \\ \psi_\pi(\alpha) &=& \min\{\beta:C(\alpha,\beta)\cap\pi\subseteq\beta\} \end{eqnarray*}\) Category:Introduction articles Category:Transfinite ordinals Category:Ordinal collapsing functions